传感器网络组网优化方法,提出了基于信息价值最大的交通传感器动态组网模型,并利用贪心算法对模型进行了求解,实现了基于任务或事件的动态组网;提出了交通传感器网络的可重构性,并对物理层上的传感器实现逻辑层上的动态组网。本发明的有益效果:实现了物理传感器的组合动态组网,把信息价值最大思想运用到传感器动态组网优化中。提出了基于事件信息价值最大的传感器动态组网模型,把贪心算法应用到传感器动态组网的优化算法中。给出了贪心算法求解动态组网优化的过程,实现了基于任务或事件的交通传感器的动态组网,并实现动态优化组网。1、一种传感器网络组网优化方法,其特征在于含有以下步骤:建立基于信 息价值最大的交通传感器动态组网模型的步骤;利用贪心算法对上述模型进行 了求解的步骤;基于任务或事件的动态组网的步骤。 2、如权利要求1所述的传感器网络组网优化方法,其特征在于建立基于信 息价值最大的交通传感器动态组网模型的步骤如下:(1)求出选择传感器的总 信息价值;(2)给出处理每个传感器的固定费用;(3)总信息价值减去固定费 用得到动态组网的信息价值。 3、如权利要求1所述的传感器网络组网优化方法,其特征在于利用贪心算 法对上述模型进行了求解的步骤如下:(1)确定各参数;(2)确定研究的事件A, 并根据事件A的性质划分与事件A有关的物理传感器,从而确定n;(3)对于事 件A,确定第一个初始解,把事件区域中心处提供的信息价值最大的传感器作为 初始解,并计算W的值;(4)以次在剩余的传感器中选择信息价值较大(已经考 虑了传感器的成本)且与此事件的相关系数较高的传感器加入模型中求解,得到 新的W值,若W值变小或不满足事先给出的约束条件,则停止计算,返回最大 的Wm和对应解集;(5)判断解集中传感器数n′,若n′<n,则重复步骤4;否 则停止计算,返回当前的Wm和解集。 4、如权利要求1述的传感器网络组网优化方法,其特征在于基于任务或事 件的动态组网的步骤如下:(1)确定任务或事件发生的地点;(2)利用权利要 求2和3的方法求出最优解;(3)确定基于此任务或事件的动态组网所选择的 传感器。 5、如权利要求2所述的传感器网络组网优化方法,其特征在于,把信息价 值最大思想用到传感器动态组网优化中。 6、如权利要求3所述的传感器网络组网优化方法,其特征在于,给出了贪 心算法求解动态组网优化的过程。 7、如权利要求3所述的传感器网络组网优化方法,其特征在于,把贪心算 法应用到传感器动态组网的优化算法中。 8、如权利要求4所述的传感器网络组网优化方法,其特征在于,提出了基 于事件信息价值最大的传感器动态组网模型。 9、如权利要求4所述的传感器网络组网优化方法,其特征在于,实现了基 于任务或事件的交通传感器的动态组网,并实现动态优化组网。 技术领域 本发明涉及一种传感器网络组网优化方法,属于交通状态检测传感器技术 领域,涉及交通传感器的动态组网,基于任务或事件的动态组网优化。 背景技术 传感器组网可以充分地利用传感器资源,增强系统的协同能力和可靠性。 而通信网络是实现各种信息正常传输的基础。一般而言,传感器组网对通信网 络有三点要求:第一,通信带宽能满足数据传输的需求;第二,通信网络的各 通信节点在功能和物理上是独立的;第三,各通信节点通信接口是通用的,也 就是说可以和不同通信系统对接。在上面三个条件的支持下,不同通信系统组 成的通信网络可以满足不同层次数据的传输要求,进而在不同的节点可以共享 各种信息数据。 在传感器组网的过程中,在逻辑层上,根据所研究的问题,对整个网络中 的传感器重新分配,使对某些特定功能的传感器数据进行集中处理,得到关于 某个时间特定的信息。同时,在另一个事件中,把与此事件的敏感的传感器的 数据集中处理,实现对此事件信息的提取。这样在物理层的传感器一定的情况 下,我们可以实现这些传感器的动态重构,而不必在物理层上移动传感器的位 置,或者说布设新的传感器。 发明内容 为了克服现有技术结构的不足,本发明提供一种传感器网络组网优化方法。 本发明提出了基于信息价值最大的交通传感器动态组网模型,并利用贪心算法 对模型进行了求解,实现了基于任务或事件的动态组网;提出了交通传感器网 络的可重构性,并对物理层上的传感器实现逻辑层上的动态组网。 本发明解决其技术问题所采用的技术方案是: 一种传感器网络组网优化方法,含有以下步骤:建立基于信息价值最大的 交通传感器动态组网模型的步骤;利用贪心算法对上述模型进行了求解的步骤; 基于任务或事件的动态组网的步骤;含有对物理层上的传感器实现逻辑层上的 动态组网的步骤。 一种传感器网络组网优化方法,建立基于信息价值最大的交通传感器动态 组网模型的步骤如下: (1)求出选择传感器的总信息价值; (2)给出处理每个传感器的固定费用; (3)总信息价值减去固定费用得到动态组网的信息价值。 一种传感器网络组网优化方法,利用贪心算法对上述模型进行了求解的步 骤如下: (1)确定各参数; (2)确定研究的事件A,并根据事件A的性质划分与事件A有关的物理传感 器,从而确定n; (3)对于事件A,确定第一个初始解,把事件区域中心处提供的信息价值最 大的传感器作为初始解,并计算W的值; (4)以次在剩余的传感器中选择信息价值较大(已经考虑了传感器的成本) 且与此事件的相关系数较高的传感器加入模型中求解,得到新的W值,若W值 变小或不满足事先给出的约束条件,则停止计算,返回最大的Wm和对应解集; (5)判断解集中传感器数n′,若n′<n,则重复步骤4;否则停止计算, 返回当前的Wm和解集。 一种传感器网络组网优化方法,基于任务或事件的动态组网的步骤如下: (1)确定任务或事件发生的地点; (2)利用权利要求2和3的方法求出最优解; (3)确定基于此任务或事件的动态组网所选择的传感器。 本发明的有益效果: 实现了物理传感器的组合动态组网,把信息价值最大思想运用到传感器动 态组网优化中。提出了基于事件信息价值最大的传感器动态组网模型,把贪心 算法应用到传感器动态组网的优化算法中。给出了贪心算法求解动态组网优化 的过程,实现了基于任务或事件的交通传感器的动态组网,并实现动态优化组 网。 附图说明 图1动态组网算法流程图; 图2实施例2路网图(数字代表传感器位置,A代表研究的事件或给定的任 务点,J代表交叉点); 图3算法执行结果图。 具体实施方式 实施例1: 一种传感器网络组网优化方法,含有以下步骤: (1)建立基于信息价值最大的交通传感器动态组网模型的步骤 步骤1:模型建立 基于信息价值最大的交通传感器动态组网模型做如下描述: max W = Σ 1 n R ik q i I i - nC 0 ]]> s . t . I i ∈ S n ≤ m ]]>此式的约束条件为物理层上的对事件A可利用的传感器。 式中: S——与事件A有关的可利用物理传感器的信息量的集合; m——与事件A有关的可利用物理传感器总数; n——选取的传感器数目; q_i——物理层传感器i被此事件利用的单位信息费用,根据上节的传感器i 使用年限内的单位信息费用为q_i,设使用年限为20年,此事件需采集i传感器 一天的信息,则q_i可按下式求出 q i = k i 20 × 365 ; ]]>I_i——物理层与事件有关的第i个传感器对此事件的信息量; C₀——处理一个传感器信息的固定费用。 上式中的ntent="drawing" img-format="tif" wi="61"/>表示各个传感器的信息价值叠和,这里考虑了各个传感器 所在路段之间的交通信息相关性,用相关系数R表示,那么各个路段的组成交 通信息的相关系数矩阵R_ij如下: ntent="drawing" img-format="tif" wi="200"/>其中R_ij=R_ji,0≤R_ij≤1。 R_ij可以通过分析i和j路段上传感器所采集的交通信息的相关性得到,上 式ntent="drawing" img-format="tif" wi="61"/>中的k表示事件发生在路段k上。 步骤2:模型分析 首先给出所要研究的事件AA,并给出事件的大致区域,这样就可以找出初始 的与事件相关性最大的传感器,同时根据区域的道路情况和传感器布置情况选 择一定数量和范围的传感器,然后确定各个参数,最后按照上述的算法对模型 求解,得到基于此事件的传感器组网方式,实现传感器的动态可重构。 在用户给出所研究的事件及与事件有关的传感器区域后,系统可以自动调 用相应的模型并进行求解,找出事件信息的满意解,用户可以设置一定的精度 或者迭代次数来控制流程;另外若对于关心的时常发生的事件,可以把相应参 数存入数据库,用户指定关心的事件,系统可以自动搜索求解;若以备忘录的 形式把之前处理事件的计算结果导入数据库,下次遇到同样的事件可直接读取 数据库中的结果,并进行微调优化,加快求解速度。 (2)利用贪心算法对动态组网模型求解的步骤 其基本思想是先确定第一步的解,然后在剩下的解空间中不断选择在目前 情况下对目标值最有利的元素,直到到达解元素个数或则目标值精度为止,若 问题满足贪心选择性质或者最优子结构性质,则最后得到的解即为最优解,否 则为满意解。 步骤1:确定各参数; 步骤2:确定研究的事件A,并根据事件A的性质划分与事件A有关的物理 传感器,从而确定n; 步骤3:对于事件A,确定第一个初始解,把事件区域中心处提供的信息价 值最大的传感器作为初始解,并计算W的值; 步骤4:以次在剩余的传感器中选择信息价值较大(已经考虑了传感器的成 本)且与此事件的相关系数较高的传感器加入模型中求解,得到新的W值,若W 值变小或不满足事先给出的约束条件,则停止计算,返回最大的Wm和对应解集; 步骤5:判断解集中传感器数n′,若n′<n,则重复步骤4;否则停止计算, 返回当前的Wm和解集。 (3)基于任务或事件的动态组网的步骤 步骤1:确定任务或事件发生的地点; 步骤2:利用贪心算法对交通传感器动态组网模型进行求解,求出最优解; 步骤3:确定基于此任务或事件的动态组网所选择的传感器。 实施例2: 选取北京市西三环和西四环处的一个路网区域,若在图示的位置(4号传感 器处)发生一起事件A(由南到北方向),考虑与此事件相关性较大的15个传感器, 见图2,这里以路网中实际的传感器布置为准。 利用上述模型: max W = Σ 1 n R ik q i I i - nC 0 ]]> s . t . I i ∈ S n < = m ]]>求解的步骤如下: 步骤1:确定参数C₀和p_iC₀表示处理一个传感器信息的固定费用,与系统有关,这里我们取60,p_i可 以由k_i算出,由于都是快速路,为简便起见,设所有的k_i相同,都为所选取的 150000,则 p i = k 20 × 365 = 20.55 . ]]>步骤2:确定各传感器与事件的相关系数 各传感器与事件的相关系数为距离的函数,即r(x)=e^-0.2632x,各交叉口距 离如表1。 表1xa0传感器之间的路线距离 xa0传感器编号路线距离传感器编号路线距离1-20.6278-J20.706
2-3
0.654
J2-9
0.6573-40.51010-112.8074-J10.64411-120.606
J1-5
0.437
12-J1
0.4995-6
0.322
J1-13
0.677
6-70.71313-141.6087-80.549J2-151.815根据各传感器与事件点A的距离,可得各传感器信息与事件A的相关系数 如表2: 表2xa0相关系数计算表 xa0传感器
编号与事件A的路段距
离x(km)
各传感器与事件A的关联系数计算xa011.791e^-0.2632x=exp(-0.2632*1.791)=0.624121.164e^-0.2632x=exp(-0.2632*1.164)=0.736130.510e^-0.2632x=exp(-0.2632*0.510)=0.874440e^-0.2632x=exp(-0.2632*1.000)=1.00051.081e^-0.2632x=exp(-0.2632*1.081)=0.752461.403e^-0.2632x=exp(-0.2632*1.403)=0.691272.116e^-0.2632x=exp(-0.2632*2.116)=0.573082.665e^-0.2632x=exp(-0.2632*2.665)=0.495994.028e^-0.2632x=exp(-0.2632*4.028)=0.3464104.556e^-0.2632x=exp(-0.2632*4.556)=0.3015111.749e^-0.2632x=exp(-0.2632*1.749)=0.6311121.143e^-0.2632x=exp(-0.2632*1.143)=0.7402131.321e^-0.2632x=exp(-0.2632*1.321)=0.7063142.929e^-0.2632x=exp(-0.2632*2.292)=0.5470155.182e^-0.2632x=exp(-0.2632*5.182)=0.2557步骤3:确定两点之间的信息 利用静态布置方法求得各传感器的信息密度函数,这里采用拟合出的指数 函数(由于实例路网较小,假设各传感器的转换因子相同,且都为快速路,都取 1.1374)得到各传感器的信息密度函数为: h(x)=a×e^-0.2632x=1.1374×e^-0.2632x所以传感器x₁到x₂处的信息为 I ( x 1 → x 2 ) = 1.1374 × ∫ x 1 x 2 e - 0.2632 x = 1.1374 × 1 - 0.2632 e - 0.2632 x | x 1 x 2 ]]> = 4.3214 ( e - 0.2632 x 1 - e - 0.2632 x 2 ) ]]>若在x₁和x₂之间的道路有交叉,设在x₁₂处,那么x₁和x₂之间的信息为: I(x₁→x₁₂→x₂) = 4.3214 ( e - 0.2632 x 1 - e - 0.2632 x 12 ) + R L 1 L 2 × 4.3214 ( e - 0.2632 x 12 - e - 0.2632 x 2 ) ]]>其中:R_L1L2——x₁所在路段L1与x₂所在路段L2之间的相关系数。 步骤4:确定路段信息相关系数矩阵 通过08年4月10日图示各传感器测得的路段速度数据,得到五个主要路 段的信息相关系数矩阵见表3: 表3xa0路段信息相关系数矩阵 xa0相关系数L1L2L3L4L5L11.00000.54900.15590.63730.3155L20.54901.00000.20840.36340.3589L30.15590.20841.00000.12350.0040L40.63730.36340.12351.00000.3520L50.31550.35890.00400.35201.0000说明:L1为1、2、3、4号传感器所在路段;L2为5、6、7、8、9号传感 器所在路段;L3为10、11、12号传感器所在路段;L4为13、14号传感器所在 路段;L5为15号传感器所在路段。 步骤5:贪心算法求解过程 逐个加入传感器到解集中,利用贪心算法,每次选入一个传感器,这里选 取传感器的规则是与事件关联系数最大的传感器首先选入,然后计算W_i,若W_i减小则停止计算,此时最大的W_i-1为最终解,此时的解集为最终解集。计算步骤 及结果见表4。 表4xa0求解计算过程 xa0检测器
编号与A的
关联系数贪心选择
步数选取的传
感器编号W值
计算结果0到1说明
W开始下降10.6241第一步4117.61020.7361第二步3255.542030.8744第三步5302.315041第四步12325.125050.7524第五步2395.863060.6912第六步13442.272070.573第七步6482.366080.4959第八步11499.0860xa090.3464第九步1549.9330100.3015第十步7576.1250110.6311第十一步14603.6220120.7402第十二步8620.0300130.7063第十三步9615.861140.547第十四步10601.339115
0.2557
第十五步
15
582.051
1
步骤6:动态组网优化结果 从表4可知,当选择12个传感器时,可得W值达到最大,此时的解集为4、 3、5、12、2、13、6、11、1、7、14、8,得到的W值为620.030。计算完毕, 最终解集见图3。